CDC25 phosphatases play a critical role in the regulation of the cell cycle and thus represent attractive cancer therapeutic targets. We previously discovered the 4-(2-carboxybenzoyl)phthalic acid (NSC28620) as a new CDC25 inhibitor endowed with promising anticancer activity in breast, prostate, and leukemia cells. Herein, we report a structure-based optimization of NSC28620, leading to the identification of a series of novel naphthylphenylketone and naphthylphenylamine derivatives as CDC25B inhibitors. Compounds 7j, 7i, 6e, 7f, and 3 showed higher inhibitory activity than the initial lead, with Ki values in the low micromolar range. Kinetic analysis, intrinsic fluorescence studies, and induced fit docking simulations provided a mechanistic understanding of the activity of these derivatives. All compounds were tested in the highly aggressive human melanoma cell lines A2058 and A375. Compound 4a potently inhibited cell proliferation and colony formation, causing an increase of the G2/M phase and a reduction of the G0/G1 phase of the cell cycle in both cell lines.